package com.xiaoyu.backtracking;

import java.util.*;

/**
 * @program: DS_and_A
 * @description: 组合总和
 *给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
 *
 * candidates中的数字可以无限制重复被选取。
 * 说明：
 *
 * 所有数字（包括target）都是正整数。
 * 解集不能包含重复的组合。
 *
 * 输入：candidates = [2,3,6,7], target = 7,
 * 所求解集为：
 * [
 *   [7],
 *   [2,2,3]
 * ]
 *
 * 什么时候使用 used 数组，什么时候使用 begin 变量?
 * 有些朋友可能会疑惑什么时候使用 used 数组，什么时候使用 begin 变量。这里为大家简单总结一下：
 *
 * 排列问题，讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时），
 * 需要记录哪些数字已经使用过，此时用 used 数组；
 *
 * 组合问题，不讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时），
 * 需要按照某种顺序搜索，此时使用 begin 变量。
 *
 * @author: YuWenYi
 * @create: 2021-05-21 17:57
 **/
public class CombinationSum_39 {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int len = candidates.length;
        if (len == 0){
            return res;
        }
        //排序是减枝的基础
        Arrays.sort(candidates);

        Deque<Integer> path = new ArrayDeque<>();

        dfs1(candidates,0,target,len, res, path);

        return res;
    }

    /**
     * @param candidates 候选数组
     * @param begin      搜索起点
     * @param len        冗余变量，是 candidates 里的属性，可以不传
     * @param target     每减去一个元素，目标值变小
     * @param path       从根结点到叶子结点的路径，是一个栈
     * @param res        结果集列表
     */
    public void dfs(int[] candidates,int begin, int target,int len,List<List<Integer>> res,Deque<Integer> path){
        if (target == 0){
            res.add(new ArrayList<>(path));
            return;
        }
        if (target < 0){
            return;
        }
        //从每一层的第 2 个结点开始，都不能再搜索产生同一层结点已经使用过的 candidate 里的元素
        // 重点理解这里从 begin 开始搜索的语意:
        //因为是可重复使用的数据,因此假设是2,3,6,7四个数据,一开始,进入根为2的递归,这里可以选择2,3,6,7
        //假设2,3,6已经遍历完成回溯回来了,此时遍历7的时候,2,3,6的分支就不需要去遍历了,因为如果有答案在前面早就已经遍历出来了!
        for (int i = begin; i < len; i++) {
            //System.out.println("递归之前 => " + path + "，剩余 = " + (target - candidates[i]));
            path.push(candidates[i]);
            //由于每一个元素可以重复使用，下一轮搜索的起点依然是 i
            dfs(candidates,i,target - candidates[i], len, res, path);
            //回溯
            path.pop();
            //System.out.println("递归之后 => " + path);
        }
    }

    //也可以考虑减枝的方式去进行回溯递归
    public void dfs1(int[] candidates,int begin, int target,int len,List<List<Integer>> res,Deque<Integer> path){
        // 由于进入更深层的时候，小于 0 的部分被剪枝，因此递归终止条件值只判断等于 0 的情况
        if (target == 0){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = begin; i < len; i++) {
            //这里剪枝，前提是候选数组已经有序
            //假设2,3,6,7,target = 7,一开始进入递归的数字是2,2,2,然后发现7-6-2 < 0,因此直接跳出2,2,2那一枝的其他分支
            //试想,7-6-2都小于0了,那么由于是有序的数组,后面的数组比2更大,因此7-6-(num>2)一定是会小于0的,因此可以大胆的直接减!
            if (target - candidates[i] < 0){
                break;
            }
            path.push(candidates[i]);
            //由于每一个元素可以重复使用，下一轮搜索的起点依然是 i
            dfs1(candidates,i,target - candidates[i], len, res, path);
            //回溯
            path.pop();
        }
    }

    public static void main(String[] args) {
        CombinationSum_39 sum39 = new CombinationSum_39();

        int[] candidates = {2,3,6,7};

        System.out.println(sum39.combinationSum(candidates, 7));
    }
}
